package vip.zhenzicheng.algorithm.leetcode.dp;

/**
 * <a href="https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/">买股票的最佳时机 [简单]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-14 14:48
 */
public class BestTimeToBuyAndSellStock_121 {

  /*普通动态规划*/
  // public int maxProfit(int[] prices) {
  //   int N = prices.length;
  //   int[][] dp = new int[N][2]; // 规定dp数组，第一列代表不持有股票最大利润，第二列代表持有股票后剩余最大钱
  //
  //   dp[0][0] = 0; // 没持有股票默认0
  //   dp[0][1] = -prices[0]; // 持有后剩余利润为负数
  //
  //   for (int i = 1; i < N; i++) {
  //     // 将昨天不持有股票的利润与持有股票在今天卖了后的利润取一个最大值
  //     dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
  //     // 将昨天持有股票的利润和今天持有股票的利润比取最大值
  //     dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
  //   }
  //   return dp[N - 1][0]; // 最大利润就是最后一次计算出来的利润值
  // }

  /*优化版动态规划*/
  public int maxProfit(int[] prices) {
    int preNotHave = 0;
    int preHave = -prices[0];

    for (int i = 1; i < prices.length; i++) {
      preNotHave = Math.max(preNotHave, preHave + prices[i]);
      preHave = Math.max(preHave, -prices[i]);
    }
    return preNotHave;
  }
}
